• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1991010186A1
    申请号:PCT/JP1990/001686
    申请日:1990-12-25
    公开日:1991-07-11
    发明作者:Syuzi Watari；Masao Watari
    申请人:Syuzi Watari；Masao Watari；
    IPC主号:G06F7-00
    专利说明:
    [0001] 明 細 書
    [0002] 高速演算方式
    [0003] 技術分野
    [0004] 本発明は、 高速演算方式に関し、 更に詳しくは全く新しい符号化 の原理に基づいて浮動小数点演算等の演算を高速に行えるようにし た高速演算方式に関する。 景技術
    [0005] 第 2 2図は従来の演算方式の構成概念図である。 C P U 1と接続 されたバス 2にメモリ 3と演算器 4 5が接続されている。 第 1の 演算器 4は、 C P IJ 1の制御下でメモリ 3から読み出されたデータ X , Yに関する 2項演算を行い、 その結果 Zを再度メモリ 3に格納 する。 一方、 第 2の演算器 5はメモリ 3から読み出したデータ Xに 単項演算を行い、 その結果 Yをメモリ 3に格納する。 つまり、 従来 の演算方式は、 メモリ 3から読み出したデータに直接演算を施すよ うになっている例が多い。
    [0006] 従来、 コンピュータの数値演算等の高速化を達成するため、 大き く分けて以下のような 5つのアプローチがなされてきた。
    [0007] ①スィツチング速度の速いデバイスの開発
    [0008] ②スィ ツチング速度の改善と高集積化のための微細加工技術の開発
    [0009] ③高速処理アーキテクチャの開発
    [0010] ④演算器の最適論理設計
    [0011] ⑤配線長の削減や冷却等の実装技術の改善
    [0012] これら 5つのアプローチの内、 ①， ②は多大な研究開発投資を必 要とし、 又③， ⑤は最終品のコス トアップに繋がる可能性が大きい 等、 性能 価格比の高い高速コンピュータ等の実現に少なからず問 題がある。
    [0013] これに対し、 ④のアプローチは純粋な論理的アプローチであるた め、 着想がよければ最も投資効率がよく、 コス トアップに繋がる心 配のないアプローチである。 しかしながら、 組合せ回路の複雑さの 理論等からこのアプローチも既にほぼ限界に達していることが指摘 されている。
    [0014] 例えば、 2つの nビッ トの 2進数の乗算器の場合、 最適論理設計 を行った時でも、 ク リティカルパスのゲ一ト段数は 0 ( 1 0 g n) 、 素子数は nの多項式オーダとなることが知られている （安浦寬人 「論理回路の複雑さの理論」 情報処理学会誌 V 0 1. 2 6 NO. 6 p p. 5 7 5 - 5 8 2 ( J u n e l 9 8 5 ) ) 。
    [0015] ここで、 ◦ ( l o g n) は l o g nのオーダとなることを示す (以下同じ） 。
    [0016] そして、 冗長 2進表現を利用した乗算器 （高木直史 「冗長 2進 加算器を用いた V L S I向き高速乗算器」 信学論 （D) , J 6 6 - D, 6 , p p. 6 8 3— 6 9 0 (昭 5 8— 0 6 ) ) や並列カウンタ 型乗算器等において、 ゲート段数が 0 ( 1 0 g n) ， 素子数が 0 (n2 ) のものが既に考案されている。 また前記冗長 2進表現を 利用した固定小数点乗算器は、 浮動小数点乗算器の仮数部の乗算器 として盛込まれ、 L S I として実現されている （H. E d a m a t s u e t a 1. ： "A 3 3 MF L O P S F l o a t i n g— P o i n t P r o c e s s o r U s i n g R e d u n d a n t B i n a r y R e p r e s e n t a t i o n" I S S C C 8 8 , p p. 1 5 2— 1 5 3 ) 。
    [0017] このような演算器の最適論理設計のアプローチは、 乗算器に限ら ず加減算器等に於いても、 ゲート段数、 素子数共にオーダ的には最 適化がほぼ達成されており、 今後大きな改善は期待できないと考え られている。
    [0018] 演算器の論理設計の課題は、 そもそも与えられた数表現 （例えば 2の補数表示の 2進数等） に対して、 その演算器の既に確定してい る入出力関係 （真理値表） を如何に論理回路で実現するかという問 題である。 そして冗長 2進表現を利用した固定小数点乗算器等は、 論理回路の内部表現に冗長 2進表現を利用することにより、 効率の よい回路を実現しているが、 この演算器の内部表現の工夫もほぼ限 界まで達していると考えられている。
    [0019] 一方、 論理回路の内部表現ではなく、 数表現ぞのものを工夫する 方向として、 剰余演算法又は数論変換法と呼ばれる方法 （有本卓 「画像のデジタル信号処理」 産業図書出版） が知られている。
    [0020] この剰余演算法を利甩したハー ドウエア （R e s i d u e N u mb e r S y s t e m :以後 RN Sと略す） は幾つかの試作が存 在する （木内淳他 「剰余演算法を用いた動画像処理用 F I Rデジタ ルフィ ルタ」 信学論 （D) ， J - 6 7 D 4, p p. 5 3 6 - 5 4 3 (昭 5 9— 0 4 ) ) 。 これらのハー ドウェアは、 固定小数点の積 和演算等を実行する代わりに、 データや係数等の固定小数点 2進数 を一度 2進数表現一 RN S変換器 （B i n a r y t o N S e n c o d e r ) を通して複数の互いに素な法の組に関する剰余の 組に変換し、 積和演算等の実行は、 各剰余の組に対して独立に行い、 一連の演算結果の剰余の組を、 中国人の剰余定理 （C h i n e s e R e m a i n d e r T h e o r e m) による RN S— 2進数表現 変換器 （RN S t o b i n a r y d e c o r d e r ) を通し て求めようとした最終結果を得る構成である。
    [0021] 2進数表現のまま積和演算を実行するより も高速演算が達成でき る理由は、 2進数のビッ ト数に比較して、 各剰余を表現するのに必 要なビッ ト数が大幅に小さ くなるため、 各法に関する演算器をコン パク ト （少ない段数と少ない素子数） に実現できるからである。
    [0022] また、 これと構成的に類似した方法として、 2進数表現一冗長 2 進数表現変換器を通して冗長 2進数乗算を行い、 冗長 2進数のまま 複数の乗算結果を累算し、 冗長 2進数表現の結果を冗長 2進数一 2 進数変換器を通すことにより、 最終的な積和演算結果を高速に計算 できるようにした信号処理プロセッサも開発されている （T. E n o m o t o , e t a 1. ： " 2 0 0MH z 1 6 b i t B i C MO S S i g n a l P r o c e s s o r " I S S C C' 8 9 D i e s t o f TH P M 1 2. 8， F e b . , 1 9 8 9 ) 。 以上、 2つのアプローチに共通した考えは、 固定小数点データを 一度、 高速演算が可能な表現データに変換し、 積和演算等の一連の 処理はこの表現のまま実行し、 最終結果を固定小数点データに戻す というものである。 前者は整数に対して成立する中国人の剰余定理 が、 後者は 1 9 6 0年代の初頭にァリ ジヱニス （A r i z i e n i s ) によって提案された冗長 2進表現 （A. A r i z i e n i s : S i g n e d— d i g i t n umb e r r e p r e s e n t a t i o n f o r f a s t p a r a l l e l a r i t h m e t i c " , I RE T r n s . E l e c . C o mp. , E C— 1 0， 3, p p. 3 8 9 - 4 0 0 (S e p t . 1 9 6 1) ) が高速 演算と元のデータに対する相互変換を保証している。
    [0023] このように、 固定小数点データに対しては、 剰余の組や冗長 2進 表現への符号化、 符号化されたデータに対する一連の演算、 結果の 固定小数点データへの復号化という構成の高速演算方式が考案され ている。 しかしながら、 演算は加減乗算に限られている点と、 何よ り も固定小数点データ以外の例えば浮動小数点データ等に対しては 適用できないという問題がある。
    [0024] 何れにしても、 固定小数点データに対しては、 符号化が高速演算 に対して有効であり、 特に冗長符号化が演算器の高速設計にも有効 であったこと等から、 固定小数点データ以外のデータに対する苻号 化も幾つか検討されている （例えば安浦、 高木、 矢島 「冗長符号化 を利用した高速並列アルゴリズムについて」 ， 信学論 （D) ， J 7 0 -D, 3 , p p. 5 2 5 - 5 3 3 (昭 6 2— 0 3 ) ， 以下文献 1 という）。
    [0025] この文献 1の中で、 冗長符号化と局所計算可能性が一般旳な形で 定義されている。 それによれば定義の部分は以下のとおりである。 冗長符号化
    [0026] Ωを有限集合とする。 Ωの要素数を | Ω Iで表す。 ∑を符号化に用 いる記号の有限集合とする。 " で 上の長さ《の全ての系列 の集合を表す。 ここで Ωのまま要素を∑ " の系列で符号化する。 ここでは、 等長符号のみを考える。 また、 Ι Ω | > 1と仮定する。
    [0027] [定義 1 ] 写像 Ψ は、 次の 2つの条件を満たすとき、 Ωに対す る∑： 上の長さ の符号化と呼ぶ。
    [0028] ( 1 ) Ψ Έ " -→Q U { Γ }, ここに ^ Ωとする。 記号 Uは和 集合を示す。
    [0029] ( 2 ) Ω中の任意の要素； Πこ対し、 Ψ (Χ') =Χとなる∑ " の要 素 X'が少なくとも 1つ存在する。 このとき、 Τを Xの符号 （c o d e ) と呼ぶ。
    [0030] 符号化の写像 を符号空間 ∑： " から原集台 と { Γ }の和集合 の上への写像として定義したので、 冗長な符号化を作ることができ る。 Ω中の 1つ以上の要素が 2個以上の符号を持つとき、 符号化は 冗長 （ r e d u n d a n t ) であるという。 第 2 3図は符号空間 ∑： " から原集合 Ωと { Γ }の和集合の上への写像を示す図である。
    [0031] ここで、 符号化 の効率を、 ∑： 上での符号化に最低限必要な符 号長と？ Fの符号長の比
    [0032] [ 1 0 g I Ι Ι Ω I ] Z«によって定義する。
    [0033] 秦を Ω上の 2項演算とする。 Ωは、 演算秦に関して閉じているとす る。 演算翁に対する ∑ " 上の 2項演算 * を次のように定義する ことができる。
    [0034] Ψ (Χ' * Υ') = Ψ (Χ') 參 Ψ (Υ') ( 1 ) 但し、 （Χ') , （y) Ε Ω、 即ち （Ω， 翁） は （ i X' ∑ " かつ Ψ (Χ') ΕΩ} ， *) に準同型である。 *は関数 F ：∑] 2"— " によって定義できる。 符号化 が冗長であれば、 関数は一義的には決まらない。 即ち、
    [0035] (1) 式を満たす r *Υ'の候補は複数存在するので、 *を定義す る Fの選択に自由度がでる。 この自由度を利用して高速に計算でき る関数 Fを選ぶことにより、 *の計算、 即ち參の計算の高速化を図 ることができる。
    [0036] F= ( f x, ί 2 , '···, ί を " から ∑： » への写像とし、 ' ί i " を Fの出力の各要素に対する部分関数とする。 各部分関数 i i ( i = 1. 2, ''·， m) がたかだかん個の入力変数 にしか依存しないとき、 Fは 一局所計算可能であるという。 この 局所計算可能性を用いて、 有限集台上の 2項演算の局所計算可能性 を定義する。
    [0037] [定義 2] 參を有限集合 Ω上の 2項演算、 Ψを ∑： 上の長さ《の の符号化とする。 拳に対する符号空間上での 2項演算 *を定義する 関数 F ： 2"→∑： " で —局所計算可能なものが存在するとき、 •は符号化 の下で k—局所計算可能であるという。
    [0038] 以上が文献 1に示された定義である。
    [0039] 文献 1に於いてはこの定義の下に、 冗長符号化と局所計算可能性が、 具体的に剰余類上の加算、 有限可換群上の演算に関して示され、 更 に整数の剰余類環に対しては加算と乗算の両方を同時に高速化する 例が示されてい 。
    [0040] しかしこのような、 冗長符号化の定義に従つた具体的符号化例は、 全て数学的に簡明な代数構造を有した集合 （剰余類、 有限可換群、 整数の剰余類環等） に対してのものであり、 例えば浮動小数点デー 夕の集台のような、 演算が群や環等の数学上の代数と直接対応がつ かないような一般的な集合に対しては何ら方法が示されていない。 つまり実用上非常に重要な浮動小数点データ等の高速演算を、 新 しい符号化を用いて達成する方式は考案されていないと言える。 従って、 本発明はこのような課題に鑑みてなされたものであって、 単項演算及び 2項演算が 1つ又は複数定義され、 これらの演算に関 して閉じた任意の集合に対して、 高速演算を可能とする符号器 （En corder)、 復号器 （Decorder)及び新しい演算器の間の関係を明らか にし、 具体的に高速な計算機等を提供することを目的と している。 発明の開示
    [0041] 本発明は、 任意の演算 （ 2項演算及び単項演算） が 1つ又は複数 定義され、 これらの演算に関して演算的に閉じた任意の有限集合に 対応するデータ （以後これを旧演算系のデータと呼ぶ） を演算する コ ンピュ一タ等の計算システム （このシステムの演算系を以後旧演 算系と呼ぶ） に対し、 前記演算を旧演算系のように演算器でそのま ま実行するのではなく、 前記データを一度符号器により一定の条件 を満足する新演算系のデータに変換し、 新演算系の演算器により一 連の演算を実行し、 得られた結果を復号器により旧演算系のデータ に戻すことにより、 必要とする演算結果を得る演算方式であって、 旧演算系のデータと新演算系のデータの相互変換を保証し、 かつ旧 演算系による演算結果と同一の結果を得ることを保証するような符 号化法により規定される符号器、 復号器及び新演算系の演算器より 構成される。
    [0042] 以下本発明の符号化法の理論的な明確化を含め、 より具体的に本 発明の内容を示す。
    [0043] 先ず、 P個の 2項演算 Ap ： Ω X Ω→Ω ( ρ = 1 , 2 , ····， Ρ) と Q個の単項演算 B q ： →Ω (q = l, 2 , *··', Q) が定義さ れ、 これらの演算に関して閉じた有限集台 Ωを考え、 集台 Ωと演算 Ap, B を合わせたもの （Ω, Ap, B J を旧演算系と呼ぶことに する。 これは例えば浮動小数点データの集合と浮動小数点演算器の ようなものである。
    [0044] そこで旧演算系の演算 Ap, B qを実行する代わりに、 集台 Ω上の データを一度符号器 Φ ： Ω→Ω'により有限集合 Ω'上のデータに変 換し、 演算 Ap, B に対応した Ω'上の演算 A' p ： Ω' X Ω'→Ω', B' q ： Ω'→Ω'を実行し、 Ω'上のデータとして得られた演算結果 を、 復号器 ■ ： Ω'→Ωで変換することにより、 本来計算しようと した Ω上の演算結果を得る構成をなすようにする。
    [0045] ここで、 有限集合 Ω'と演算 Α' ρ, B'，及び符号器 Φ， 復号器 を合わせたもの （Ω', Α' Ρ, B ' Q, Φ, Ψ) を新演算系と呼ぶこ とにする。 このとき、 新演算系 （Ω'， Α'ρ, Β' ， Φ, Ψ) と旧 演算系 （Ω, Ap, B J との間に、 以下の （ 2 ) 〜 （ 5 ) の 4式に よる条件を課すことにより、 データの相互変換の保証及び演算結果 の同等性、 つまり前述した 0による符号化、 A' p, B、による演算、 による復号化という一連の流れによる結果と旧演算系による結果 がー致することを保証する。
    [0046] Ω上の任意の要素 Xに対して、 Ω'上の部分集合で以下の 4式を 満足する [X] を対応させる。 このとき、 集合族 {[ ]} xsa を集合 Ωの集合 Ω'上の符号と呼ぶことにする。
    [0047] この符号と新演算系 （Ω', A' p, Β' ,, , Ψ) の間に次の条 件を課す。
    [0048] Ωである全ての Xに対して
    [0049] Φ (X) ≡ [X] 匚 Ω' ( 2 )
    [0050] Ωである全ての Xに対して
    [0051] Ψ ( [X] ) =Χ≡ Ω ( 3 ) X, ： である全ての X, Υ、 及び ρ≡ { 1 , 2， . ， P: である全ての Ρに対して、 として
    [0052] Ζ = ΑΡ (X, Υ) « [Ζ] コ A' p ( [X] , [Y ) ( 4)
    [0053] である全ての X、 及び q E { 1 , 2 , ··'* , 0} である全ての qに対して、 として
    [0054] Υ= Β , (X) [Yl コ B'q ( [X] ) ( 5 ) ここで Φ (X) ≡ [X] は、 Φ (X) が Ω'の部分集合 [X] の要 素であることを示す。 また は同値であることを示し、 ( [X] ) 等は、 集合 [X] の写像？ Πこよる像を表す。 例えば （ 5 ) 式の《記 号の右辺の [ ] コ B'q ( [X] ) は " X' E [X] である全て の に対して、 Β' (Χ') ≡ [Yl " なる命題に等しい。
    [0055] 前記した （ 2 ) 式は符号化時の関係を、 （ 3 ) 式は復号化時の関 係を、 （ 4 ) 式は 2項演算時の新、 旧演算と符号の関係を、 （ 5 ) 式は単項演算時の新、 旧演算と符号の関係をそれぞれ表している。
    [0056] ( 3 ) 式から である全ての: 5Πこ対して
    [0057] IX] ^0 ( 6 )
    [0058] X, である全ての X， ： Tに対して
    [0059] χ^γ<^> [X] π [r] =ø ( 7 ) が成立する。 ここで、 0は空集台を意味する。
    [0060] ( 6 ) 式は、 若し [X] =0ならば、 ([X])= (0) = 0で ( 3 ) 式に矛盾する。 また、 （ 7 ) 式は若し [X] Π [Y ^0 ならば Z' E [X] かつ Ζ, [>] が存在するから、 （ 3 ) 式 より χ= Ψ ( は] ) コ Ψ (ζ') ciw ( [ ] ) =γ
    [0061] つまり Χ= となり、 矛盾するという具合に証明される。
    [0062] ( 6 ) 、 ( 7 ) (つまり （ 3 ) 式） と （ 2 ) 式より明らかに
    [0063] I Ω' I≥ I Ω Iでなければならない。 また [X] は少なく とも 1 つ要素を含むものである。
    [0064] そこで、 全ての Xに対して [X] が唯 1つの要素からなる場台、 符号 { [X] } xsa を非冗長符号と呼び、 その他の場合符号
    [0065] { [X] } 。 を冗長符号と呼ぶことにする。
    [0066] C = U xea [XI , Nc = Ω' - C ( 8 ) とすると、 Cは符号の全体集台であり、 Ncは非符号の集合である。 本発明における写像 の値域は Ωであり、 前記文献 1の写像 の 値域 Ω υ {Γ} とは異なる。 つまり本発明の写像 は旧演算系の データ集合 Ωへの全射であるが、 前記文献 1の写像 ·は Ωへの全射 ではなく、 Ω υ {Γ} への全射である。
    [0067] 第 2図は本発明の写像 と定義域 Ω' = C U NCと値域 Ωの関係を 示す図である。 第 2 3図に示す従来の写像関係とは異なっている。 第 2図からも解るように、 本発明においては写像 は、 復号器に 完全に対応するものとなる。
    [0068] また、 定義式 （2 ) 〜 （ 5 ) が符号 { [X] } Χ ΕΩ が冗長符号 であるか、 非冗長符号であるかに依存しない定義式であるため、 高 速化に有効な符号を、 必ずしも冗長符号に限定している訳ではなく、 非冗長符号も選択の対象となる。 つまり （2 ) 〜 （ 5 ) 式を満足す る Φ， Ψ, A B' q, { ίΧΐ } xsa は全て旧演算系と同じ 演算結果を導き得る演算方式となる。
    [0069] これ等の新演算系や符号は、 一般的に超天文学的ともいえる莫大 な数が存在する。 これらの内、 高速化効率や符号化効率等の具体的 評価基準から望ましいものを選択することで、 実際の高速演算のた めの符号器、 復号器、 各演算器を決定し、 具体的システムを構成す るというのが本発明の骨子である。
    [0070] 本発明で述べた選択の自由度は、 例えば B = { 0 , 1} として、 Ω = B "、 且つ I Ω' I = I Ω I (符号は非冗長符号） の場合、 Φは 2"個の要素の置換、 は Φの逆置換と見なせることから、 選択の 対象の数は 2" ！ という莫大な数となる。 また、 当然のこととして I Ω' I > I Ω I なる場合はさらに大きな自由度がある。
    [0071] このように本発明で述べた選択の自由度は、 前記文献 1で述べら れている選択の自由度と質的にも違いがあり、 また飛躍的に大きな 自由度を持つ。 このことは前記文献 1に 「符号化 が冗長であれば、 Fはユニークには決まらない。 即ち、 （ 1 ) 式を満足する の候補は複数存在するので、 *を定義する Fの選択に自由度がでる < 我々は、 この自由度を利用して高速に計算できる Fを選ぶことによ り、 *の計算、 即ちきの計算の高速化を計る」 と記載されているこ とから、 前記文献 1では、 ある与えられた冗長符号に対して、 冗長 符号故に生ずる演算器の決定の自由度を利用するものであったこと からも明らかである。
    [0072] また、 この選択の自由度の飛躍的増大の他、 前記文献 1の が Ω と不明解な集台 {厂} の和集合への写像であったことから、 は復 号器と直接対応づけができなかった。
    [0073] その点、 本発明における？ は常に復号器と対応しており、 具体的 に回路設計ができる利点がある。 図面の簡単な説明
    [0074] 第 1図は、 本発明にかかる好ましい符号器， 復号器， 演算器， と G P ϋとの関係を示すプロック図であり、 第 2図は本発明の写像 と定義域 Ω ' - Cリ1^ (：と値域2との関係を示す図、 第 3図乃至第 5 図は旧演算系の具体例である 2項演算 Α， Β及び単項演算 Cにおけ るそれぞれの演算規則の説明図、 第 6図乃至第 8図は旧演算系によ る演算器 A , Β , Cのそれぞれの回路例を示す図、 第 9図は実施例 における新演算系の符号を示す図、 第 1 0図乃至第 1 2図は旧演算 系の A , Β , Cのそれぞれに対応した実施例における新演算系の 2 項演算 A '， B '及び単項演算 C 'の演算規則を示す図、 第 1 3図は 実施例における符号器の対応を示す図、 第 1 4図は実施例における 復号器の対応を示す図、 第 1 5図乃至第 1 9図は実施例における新 演算系のそれぞれ 2項演算 Α '， Β ' , 単項演算 C '， 符号器 Φ及び 復号器 の回路図、 第 2 0図は各ゲー 卜の素子数と遅延時間を示す 図、 第 2 1図は旧演算系の具体例と新演算系の実施例の素子数と遅 延時間の比較を示す図、 第 2 2図は従来の代表的な演算方式の構成 概念図、 第 23図は文献 1に示されている符号空間 "から原集 台 Ωと {Γ} の和集台への写像 を示す図である。
    [0075] 第 1図において、
    [0076] l'，'C PU、 2 ···-データバス、 3 ·'·メモリ、 10·'，符号器、
    [0077] 11, 12 ···演算器、 13，··復号器。 発明を実施するための最良の形態
    [0078] 本発明をより詳細に説述するために、 添付の図面に従ってこれを 説明する。
    [0079] 第 1図は、 本発明にかかる好ましい符号器， 復号器， 演算器 （新 演算系） と C PUとの関係を示すブロック図であり、 これは第 22 図に示された従来の代表的な演算方式 （旧演算系） に対応する形で 記載されている。 新演算系、 旧演算系の演算の対応を示す意味で 2 項演算には # 1、 単項演算には # 2なる同一の番号が両方の演算系 に付されている。 第 22図のような従来の旧演算系の計算システム では、 メモリ上のデータを C P IJ 1の制御下で演算器に送り込み演 算結果を得る方式であつた。
    [0080] 一方、 第 1図に示される本発明にかかる好ましい演算方式では、 メモリ上の旧演算系のデータ、 例えば x、 ： rは先ず C PU 1の制御 下で符号器 Φに送り込まれ、 それぞれ T、 ： なる新演算系のデ一 夕に変換されメモリに格納される。 次にメモリ上の新演算系のデ一 タを C P U 1の制御下でメモリから新演算系の演算器に送り込み、 演算器から出て来る新演算系の演算結果をメモリに格納する。 目的 とする一連の演算 （例えば積和演算や、 べク トル演算、 マ ト リ ック ス演算等） は、 この新演算系の演算の繰り返しにより実行する。 所 定の演算が終了した時、 メモリ上には最終結果の新演算系のデータ が得られる。 このデータを C P U 1の制御下で復号器 こ送り込み. 所望の旧演算系の結果を得る方式である。 このとき第 1図の繰り返し演算に使用される新演算系の演算は、 第 2 2図における旧演算系に演算より、 一般に大幅な高速化が達成 できる。 このことをより具体的に説明するため、 以下本発明の実施 例について説明する b
    [0081] Ωを 8個の要素からなる有限集合とし、
    [0082] Ω = {X0, Xi, X2, ', Χι] とする。
    [0083] この Ω上に 2つの 2項演算
    [0084] A ： Ω X Ω— Ω , B ： Ω X Ω→Ω
    [0085] と 1つの単項演算
    [0086] C ： Ω→Ω
    [0087] が定義されている。 この演算の規則をそれぞぇ第 3図乃至第 5図に 示す。 第 3図， 第 4図は 2項演算 Α， Βの演算規則を、 第 5図は単 項演算 Cの演算規則をそれぞれ示す。 更に、 この Ωは、 ブール値 { 0 , 1 } の 3個の系列で次のように符号化されているものとする。
    [0088] Χ0 = { 0 , 0, 0} ， Χι = { 0, 0, 1 }
    [0089] 2 = { 0, 1, 0 } ， Χζ = { 0 , 1 , 1 }
    [0090]
    [0091] Xs = { 1 , 1 , 0 } ， 7 = { 1 , 1 , 1 }
    [0092] この時、 2項演算 Α及び Βは、 6変数の 3個のブール関数で表わせ、 回路は 6入力 3出力の組合わせ回路で実現することができる。 同様 に単項演算 Cは 3変数の 3個のブール関数で表わせ、 回路は 3入力 3出力の組合わせ回路で実現することができる。
    [0093] 演算 Αを表す 3個のブール関数を
    [0094] a { 0, 1 } 3 X { 0 , 1 } 3-* { 0 , 1 } ( i = 0 , 1 , 2 ) と し、 入力の Ωの 2要素に対応する変数のブール値系列をそれぞれ ( 2 , x i , x。） ， （y 2, y i , y。） で表せば
    [0095] a 0 (x2, X i, Xo, Ύ 2 , Ύ l, Ύ o)
    [0096] = l + xo + i + yo + y i + xo yo + o y i + 1 y 0 + 1 y 1 a i ( x 2 , x l , o , y 2 , y i , y。)
    [0097] = o + xi + y o + y i + o y o + o y i + x i y o + i y i + 2 y + x2 y 0 y i + o i y 2 + x o X i y o i
    [0098] a 2 ( X 2 , X l , 0 , Y 2 , Y l , Ύ o )
    [0099] = l + 0 H- yo + o yo + x2 y2 + x 2 y o y i + o i y 2
    [0100] + 2 Υθ Υ2 + θ Χ2 Υ2 + 2 Υ ΐ Υ2 + Χ ΐ 2 Υ2 + θ Χ ^θ Υ ΐ
    [0101] + x0 2 y i y2 + t X 2 y o y 2 + i X2 y i y2 + o X 2 y o y i
    [0102] + x o x i y o y 2 + x l x 2 y o y i + x D x i y i y 2
    [0103] 同様に演算 Bを 3個のブール関数
    [0104] b i ： { 0 , 1 } 3 x { 0 , 1} 3→ {0, 1 } ( i = 0， 1， 2 ) また、 演算 Cを 3個のブール関数
    [0105] c i ： {0, 1} 3→ { 0, 1} ( i = 0, 1 2 )
    [0106] とすると、
    [0107] b o 2, 1 , X 0 , y 2 , y 1 , y 0 )
    [0108] = l + x。 y。 + x:。 y i + X i y Q + X i y i
    [0109] b 1 ( 2 , x 1 , 0 , y 2 , y 1 , y 0 )
    [0110] = o y i + i y o + x i y i
    [0111] b 2 ( x 2 , l , 0 , y 2 , y 1， y 0 )
    [0112] = 2 + y 2 + o i + y o y l + o y o y i
    [0113] + Χ0 Χ ι Υο + Χο Χ ι Υο Υ ι
    [0114] C o ( X 2 , 1 , o ) = X 2 + X o X i
    [0115] C 1 ( 2 , 1 , X。 ) = X。 + X 2 + X。 X 1
    [0116] C 2 ( X 2 , X I , X 0 ) = Χ θ + Χ ΐ + Χ 2 + Χ θ Χ 2
    [0117] のようにブール環の論理式で表すことができる （勿論、 これ等はブ —ル朿でも表すことができる） 。
    [0118] そこで、 このような論理式で与えられる演算系 （Ω, A, B, C) を旧演算系とする。 第 6図乃至第 8図はそれぞれ演算 A, B, Cを 2入力 AND, 2入力 E X OR及び NOTの各ゲ一トにより組台わ 5 せ回路と して実現したもので、 何れも旧演算系の回路である。
    [0119] これ等旧演算系に対して、 （ 2 ) 式〜 （ 5 ) 式を満足する符号化 { [XI ) ； ^Ω と して、 ここでは非冗長符号の例を示す。
    [0120] 第 9図は （ 2 ) 式〜 （ 5 ) 式を満足する数多 （この場合 23 ！種） の新演算系 （Ω', Α', Β', C', Φ, Ψ) の内、 演算 Α', Β', C'の論理式が、 極力少ない変数に依存するように、 コンピュータ を利用して符号を選んだ例の図である。 ここで Ω'も 8個の要素か らなる有限集台とし、 Ω' = {ΧΌ, Χ , Χ'2, ···'"， Χ'Ί) であるものとする。 更に、 この Ω'も Ωと同様にブール値 { 0, 1 } の 3個の系列で次のように符号化されているものとする。
    [0121] ΧΌ = 0 0， 0} ΧΊ = 0 0 1 }
    [0122] Χ、= 0 1, 0} Χ'3 = 0 1 }
    [0123] Χ = 1 0, 0} 0 1}
    [0124] Χ、- 1' 0} ΧΊ = 1 1 1}
    [0125] このとき、 Ω'上の演算
    [0126] Α' ： Ω' Χ Ω'-*Ω', Β ' Ω' X Ω'→ Ω'， C ' ： Ω'-→Ω
    [0127] の演算規則は、 それぞれ第 1 0図乃至第 1 2図に示されたものにな る。 また、 第 9図で示されている符号に対応した符号器 0の対応図 (ブール値に翻訳すれば真理値表） は第 1 3図に、 復号器 の対応 図は第 1 4図に示すようなものとなる。
    [0128] 更に、 Α， Β, Cと同様に、 A'， B'は 6変数, C'， は 3変数のそれぞれ 3個のブール関数で表せる。 Ω'上のブール値 3 個の系列の変数を （χ'2， χΊ. χΌ) , ( y '2, y Ί, y Ό) 等 で表し、 Α'， B'のブール関数を i = 0, 1 , 2に対し、 それぞれ a ' if b ' ·, ： { 0 , 1 } 3 x { 0 , 1！ 3→ { 0 , 1 }
    [0129] C'， , のブール関数を i = 0 , 1 , 2に対し、 それぞれ c ' φ i ： { 0 , 1 } 3→ { 0 , 1 }
    [0130] と表せば、 それぞれ以下のようなブール環の論理式で表せる。 6 a o ( X ' 2 , X x 0 , y 2 , y y Ό ) = x ' y Ί
    [0131] a ' i ( ' 2. X X 0 , y ' 2 , y y ' o )
    [0132] = ' 2 + y ' 2 + X 2 y
    [0133] a ' 2 ( '2, X ' X y 2 , y y ' o ) = 1 + x ' 0 y b '0 ( x ' 2 , X X y ' 2 y yO) = x Ό + y Ό
    [0134] b' x ( x ' 2 X X y ' 2 y y ' o ) = ' z y ' 2
    [0135] b '2 ( ' 2 X X y '2 y yO)
    [0136] = x Ί + Ύ + X y
    [0137] C ' o ( ' 2 X ' X ' 0 ) = x ' 2
    [0138] C ' i ( X ' 2 X X ' 0 ) = 1 + x Ό
    [0139] C ' 2 ( ' 2 , X ' 0 ) = 1 + x Ί
    [0140] Φ o ( X 2， X。 ) = 2 + X 0 X
    [0141] Φ ( 2 , X I , X。 ) = 1 + X o
    [0142] Φ ( X 2 , x。) = 0 + X
    [0143] Ψ ( X '2 , x , x ' 0 ) = 1 + X ' i
    [0144] Ψ ( X ' 2 x , X ' 0 ) = 1 + x Ί + x ' 2
    [0145] ^2 ( X ' 2 x 0 ) = 1 + X '。 + X ' i + X + X X
    [0146] 第 1 5図乃至第 1 9図は、 それぞれ演算 A', B'， C'及び符号 器 Φ， 復号器 を 2入力 AND, 2入力 E X OR及び NO Tの各ゲ ―トにより組台わせ回路として実現したものである。 そこでこれら の新演算系 （Ω', Α', Β'. C', Φ, Ψ) の各回路を搭載した場 合と、 第 7図， 第 8図及び第 9図の旧演算系の各回路を搭載した場 合の違いを比較するため、 各回路のトランジスタ素子数 （以下単に 素子数という） とク リティカルパスの遅延時間 （以下単に遅延時間 という） を、 AND, E XOR及び NOTの素子数と遅延時間を基 に示す
    [0147] 第 2 0図は、 各ゲー卜の素子数と遅延時間を、 N OTの素子数を □， 遅延時間を△として示したものである。 この第 2 0図と各回路図から旧演算系， 新演算系の各回路の素子 数， 遅延時間を示したのが第 2 1図である。 この図から分かるよう に、 旧演算系の演算器 A, B, Cに比較して、 新演算系の演算器 Α', Β', C'は素子数， 遅延時間共に大幅に削減されている。
    [0148] このことは、 例えば上記の 3種の演算器が 1台ずつ搭載され、 各 演算が同じクロックサイクルで実行されるようなノィマン型の計算 機システムの場合、 旧演算系のシステムと新演算系のシステムのク ロックのサイクルタイムの比は 4 ： 1となり、 新演算系のシステム の演算処理能力が旧演算系のシステムの 4倍になることを意味する。
    [0149] (但し、 サイクルタイムは最も遅い演算器により決定されることを 前提とした） 。 また、 旧演算系のシステムの総素子数が 1 0 1ロで あるのに対し新演算系のシステムの演算器， 符号器及び復号器の総 素子数は 4 4□と半分以下になる。
    [0150] 次に、 各演算器を N個搭載し、 演算を完全に並列実行するような 非ノイマン型の計算システムの場合、 サイクルタイムの比はノイマ ン型と同じであるが、 素子数の削減効果はより顕著となる。 つまり、 新演算系の並列システムにおいて、 符号器， 復号器は並列度 Nと無 関係に 1台ずつ搭載すれば十分と考えれば、 十分大きな並列度 Nの 場台、 システムの素子数の比は、 演算器の素子数の比 （ 1 0 1 : 2 1) に近づく。 つまり、 総素子数は約 1Z 5となる。
    [0151] 以上のように、 Ω上の演算的に閉じた 3つの演算 A, B, Cに対 して （ 2 ) 式〜 （ 5 ) 式の 4つの条件を満足する数多くの新演算系 の中には、 高速化や素子数の削減の目的に対して有効なものが存在 することを具体的に示すことができる。 本発明における符号の定義 式 （ 2 ) 式〜 （ 5 ) 式に現れる全ての写像 Αρ, Β 及び A' p. B' q ， Φ， ？ は全て直接回路と対応がとれたものであるため、 この実施 例の具体的回路も容易に導く ことができる。
    [0152] 以上説明したように、 本発明における符号の定義 （ 2 ) 式〜 （ 5 ) 式によれば、 新演算系 （Ω', A' p, B'q， Φ， Ψ) の Ω'を
    [0153] I Ω' I ≥ I Ω I となるように選び （前記実施例では I ΩΊ = I Ω 1)、 符号 { [X] } χ^α を逐次選択し、 A'p, B' qが （ 4 ) , ( 5 ) 式を満足する条件の下に所望の条件を満足するものをコンピュータ 等を利用して選んでいく。
    [0154] つまり、 Ω'の選択， 符号 { [ ] } xs a の選択及び A' P， B' qの選択という 3段階の選択の自由度があり、 その自由度の中か ら満足するものを選択することにより、 少なく とも旧演算系より も 素子数及び遅延時間の両面で改善ざれた新演算系を決定することが
    [0155] It) 可能となる。 なお、 上述した実施例においては、 I Ω' 1 = I Ω I とし、 その結果として各 [X] である全ての Xに対して） が 1つの要素しか有しない非冗長系について述べたが、 i Ω' I > I Ω I の場合の冗長符号及び非冗長符号の何れに対しても上述した 実施例と同様またはそれ以上 （選択の自由度が更に拡大されるため）
    [0156] 15 の効果を得ることができることは容易に理解することができる。
    [0157] また、 上述した実施例においては、 新演算系の各演算器の変数依 存度を可能な限り少なくなるような規準で符号を選択したが、 この 規準は他の規準に置き換えても同様である。
    [0158] 以上、 詳細に説明したように、 本発明によれば演算的に閉じた任
    [0159] 20 意の旧演算系に対して少なく とも旧演算系より も任意の規準に対し て優位なる新演算系を構成することができ、 本発明の定義における 写像が具体的回路と直接対応がとれているために、 具体的ハー ドウ エアを実現することができる。
    [0160] 25 産業上の利用可能性
    [0161] コンピュータ等の演算の高速化及び素子数の削減による低価格化 等に非常に有効である。 特に並列演算型の計算システムにおいてよ り顕著な効果を発揮する。
    权利要求:
    Claims
    請 求 の 範 囲 任意の演算 （ 2項演算及び単項演算） が 1つ又は複数定義され、 これらの演算に対し演算的に閉じた任意の有限集合に対するデータ (旧演算系のデータ） を演算するコンピュータ等の計算システムに 対し、 前記演算を旧演算系のように演算器でそのまま実行するので はなく、 前記データを一度符号器により新演算系のデータに変換し、 新演算系の演算器により一連の演算を実行し、 得られた結果を復号 器により旧演算系のデータに戻すことにより、 必要とする演算結果 を得る演算方式であって、 旧演算系のデータと新演算系のデータの 相互変換を保証し、 かつ旧演算系による演算結果と同一の結果を得 ることを保証するような符号化法により規定される符号器， 復号器 及び新演算系の演算器を具備し、 前記手順の演算を実現するように 構成した高速演算方式。
    类似技术:
    公开号 | 公开日 | 专利标题
    Koren2018|Computer arithmetic algorithms
    Mohan et al.2016|Residue number systems
    Piestrak1994|Design of residue generators and multioperand modular adders using carry-save adders
    LEWIN2013|Design of logic systems
    Ma et al.1990|Multiplier policies for digital signal processing
    US6032170A|2000-02-29|Long instruction word controlling plural independent processor operations
    US5590350A|1996-12-31|Three input arithmetic logic unit with mask generator
    US4281391A|1981-07-28|Number theoretic processor
    US5696954A|1997-12-09|Three input arithmetic logic unit with shifting means at one input forming a sum/difference of two inputs logically anded with a third input logically ored with the sum/difference logically anded with an inverse of the third input
    US5634065A|1997-05-27|Three input arithmetic logic unit with controllable shifter and mask generator
    US6098163A|2000-08-01|Three input arithmetic logic unit with shifter
    US5680339A|1997-10-21|Method for rounding using redundant coded multiply result
    US5606677A|1997-02-25|Packed word pair multiply operation forming output including most significant bits of product and other bits of one input
    US5465224A|1995-11-07|Three input arithmetic logic unit forming the sum of a first Boolean combination of first, second and third inputs plus a second Boolean combination of first, second and third inputs
    US5596763A|1997-01-21|Three input arithmetic logic unit forming mixed arithmetic and boolean combinations
    Hu et al.1991|Expanding the range of convergence of the CORDIC algorithm
    US5805913A|1998-09-08|Arithmetic logic unit with conditional register source selection
    US5485411A|1996-01-16|Three input arithmetic logic unit forming the sum of a first input anded with a first boolean combination of a second input and a third input plus a second boolean combination of the second and third inputs
    US5640578A|1997-06-17|Arithmetic logic unit having plural independent sections and register storing resultant indicator bit from every section
    US5960193A|1999-09-28|Apparatus and system for sum of plural absolute differences
    Garner1965|Number systems and arithmetic
    US6058473A|2000-05-02|Memory store from a register pair conditional upon a selected status bit
    Wang et al.1997|Hybrid CORDIC algorithms
    CA1041212A|1978-10-24|Fast fourier transform stage using floating point numbers
    Lu2004|Arithmetic and logic in computer systems
    同族专利:
    公开号 | 公开日
    EP0507946A4|1993-09-01|
    CA2072254A1|1991-06-29|
    EP0507946A1|1992-10-14|
    JPH03201114A|1991-09-03|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1991-07-11| AK| Designated states|Kind code of ref document: A1 Designated state(s): CA US |
    1991-07-11| AL| Designated countries for regional patents|Kind code of ref document: A1 Designated state(s): AT BE CH DE DK ES FR GB GR IT LU NL SE |
    1992-06-24| WWE| Wipo information: entry into national phase|Ref document number: 2072254 Country of ref document: CA |
    1992-06-26| WWE| Wipo information: entry into national phase|Ref document number: 1991900925 Country of ref document: EP |
    1992-10-14| WWP| Wipo information: published in national office|Ref document number: 1991900925 Country of ref document: EP |
    1994-12-15| WWW| Wipo information: withdrawn in national office|Ref document number: 1991900925 Country of ref document: EP |
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]